package com.salim.leetcode.$146;

import com.salim.leetcode.$109.ConvertSortedListToBinarySearchTree;
import lombok.extern.slf4j.Slf4j;

import java.util.*;

@Slf4j
public class LRUCache {
    private ListNode header = new ListNode(-1,-1);
    private ListNode tail = new ListNode(-1,-1);
    private Map<Integer, ListNode> cache = new HashMap<>();
    private int length;
    public LRUCache(int capacity) {
        length = capacity;
        header.next = tail;
        tail.prev = header;
    }

    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }
        ListNode node = moveKeyToHeader(key);
        return node.val;
    }

    private ListNode moveKeyToHeader(int key) {
        ListNode node = cache.get(key);
        //将node.prev和node.next连接
        node.prev.next = node.next;
        node.next.prev = node.prev;

        //将node指向队头
        node.next = header.next;
        header.next = node;
        node.next.prev = node;

        node.prev = header;
        return node;
    }

    public void put(int key, int value) {
        if(cache.size()==length && !cache.containsKey(key)){
            //删除队尾
            tail.prev.prev.next = tail;
            cache.remove(tail.prev.key);
            tail.prev = tail.prev.prev;
        }
        if(cache.containsKey(key)){
            ListNode node = moveKeyToHeader(key);
            node.val = value;
        }else{
            ListNode currentHeader = new ListNode(key,value);
            currentHeader.prev = header;
            currentHeader.next = header.next;
            header.next = currentHeader;
            currentHeader.next.prev = currentHeader;
            currentHeader.val = value;
            cache.put(key,currentHeader);
        }

    }

    public class ListNode {
        int key;
        int val;
        ListNode next;
        ListNode prev;
        ListNode() {}

        @Override
        public boolean equals(Object o) {
            return this == o;
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }

        ListNode(int key, int val) {this.key = key; this.val = val; }
    }

    public static void main(String[] args){
        LRUCache lRUCache = new LRUCache(2);
        // cache is {1=1}
        lRUCache.put(1, 1);
        // cache is {1=1, 2=2}
        lRUCache.put(2, 2);
        // return 1
        log.info("{}",lRUCache.get(1));
        // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
        lRUCache.put(3, 3);
        // returns -1 (not found)
        log.info("{}",lRUCache.get(2));
        // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
        lRUCache.put(4, 4);
        // return -1 (not found)
        log.info("{}",lRUCache.get(1));
        // return 3
        log.info("{}",lRUCache.get(3));
        // return 4
        log.info("{}",lRUCache.get(4));
    }
}
